package com.demo.datastructure.reorder.quickSort;

/**
 * @description: 利用快速排序，在O(n)时间复杂度内找到第k大元素
 * @author: ljr
 * @time: 2021/5/4 18:02
 */
public class MyQuickSort4 {


    public static void quickSort(int[] args, int n, int k){
        quickSortC(args,0,n-1, n-k);
    }

    private static void quickSortC(int[] args, int p, int r, int k) {
        if(p >= r){ return;}
        int q = partition(args,p,r);
        if(q == k){
            return;
        }else if(q > k){
            quickSortC(args,p,q-1, k);
        }else{
            quickSortC(args,q+1,r,k);
        }
    }

    private static int partition(int[] args, int p, int r) {
        int pivot = args[r];
        int min = p;
        for(int i = p; i < r; i++){
            if(args[i] < pivot){
                int val = args[i];
                args[i] = args[min];
                args[min++] = val;
            }
        }

        int val = args[min];
        args[min] = pivot;
        args[r] = val;
        return min;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{11,8,3,9,7,1,2,5};
        MyQuickSort4.quickSort(nums,8, 2);
        System.out.println(nums[8-2]);
    }
}
